The number of shortest paths from point A to | vedclass

Name: Exam Paper Generator | JEE NEET Paper Generator | Vedclass
Brand: Vedclass
Rating: 5 (35 reviews)

Question

(B) To find the number of shortest paths from $A$ to $D$,we observe that all paths must pass through the segment $MN$. Let $S_M$ be the set of paths f

Vedclass · Accepted Answer

$186$

Vedclass · Answer

(B) To find the number of shortest paths from $A$ to $D$,we observe that all paths must pass through the segment $MN$. Let $S_M$ be the set of paths from $A$ to $M$ and $S_N$ be the set of paths from $A$ to $N$. Paths from $A$ to $M$: The grid from $A$ to $M$ is $2$ units wide and $5$ units high. The number of paths is $\frac{(2+5)!}{2!5!} = \frac{7!}{2!5!} = 21$. Paths from $M$ to $D$: The grid from $M$ to $D$ is $2$ units wide and $2$ units high. The number of paths is $\frac{(2+2)!}{2!2!} = \frac{4!}{2!2!} = 6$. Total paths through $M$ = $21 	imes 6 = 126$. Paths from $A$ to $N$: The grid from $A$ to $N$ is $2$ units wide and $4$ units high. The number of paths is $\frac{(2+4)!}{2!4!} = \frac{6!}{2!4!} = 15$. Paths from $N$ to $D$: The grid from $N$ to $D$ is $2$ units wide and $3$ units high. The number of paths is $\frac{(2+3)!}{2!3!} = \frac{5!}{2!3!} = 10$. Total paths through $N$ = $15 	imes 10 = 150$. Since the segment $MN$ is a single vertical step,any path passing through $M$ must pass through $N$ (or vice versa depending on direction). However,the grid structure shows $M$ is above $N$. Thus,any path from $A$ to $D$ must pass through the segment $MN$. The number of paths through $MN$ is the number of paths from $A$ to $N$ multiplied by the number of paths from $M$ to $D$. Paths through $MN = (	ext{Paths } A 	o N) 	imes (	ext{Paths } M 	o D) = 15 	imes 6 = 90$. Using the Principle of Inclusion-Exclusion for paths through $M$ or $N$: Total paths = (Paths through $M$) + (Paths through $N$) - (Paths through both $M$ and $N$) Total paths = $126 + 150 - 90 = 186$.

The number of shortest paths from point $A$ to $D$ (as shown in the figure) is:

Similar Questions

Consider the set of all triangles $OPQ$ where $O$ is the origin and $P$,$Q$ are distinct points in the plane with non-negative integral coordinates $(x, y)$ such that $5x + y = 99$. The number of such distinct triangles whose area is a positive integer is:

There are $6$ multiple choice questions on an examination. How many sequences of answers are possible,if the first three questions have $4$ choices each and the next $3$ have $5$ each?

How many different signals can be transmitted by arranging $3$ red,$2$ yellow and $2$ green flags on a pole? [Assume that all the $7$ flags are used to transmit a signal.]

The number of ways in which $5$ boys and $3$ girls can be seated on a round table if a particular boy $B_1$ and a particular girl $G_1$ never sit adjacent to each other,is

In how many ways can a committee consisting of one or more members be formed out of $12$ members of the Municipal Corporation?

Vedclass Test Series

Exam Paper Generator

Online Exam Module